#include<bits/stdc++.h>
typedef struct GNode{
	int Nv;
	int Ne;
	int G[100][100];
	int visited[100];
}*MGraph;
typedef struct ENode{
	int v1,v2;
}*Edge;
typedef struct QNode{
	int data[100];
	int front,rear;
}*Queue;
MGraph createGraph(MGraph graph,int v,int e){
	graph=(MGraph)malloc(sizeof(struct GNode));
	graph->Nv=v;
	graph->Ne=e;
	for(int i=0;i<graph->Nv;i++){
		for(int j=0;j<graph->Nv;j++){
			graph->G[i][j]=0;
		}
	}
	for(int i=0;i<graph->Nv;i++){
		graph->visited[i]=0;
	}
	return graph;
}
void insertEdge(MGraph graph,Edge e){
	graph->G[e->v1][e->v2]=1;
	graph->G[e->v2][e->v1]=1;
}
MGraph buildGraph(MGraph graph){
	Edge e=(Edge)malloc(sizeof(struct ENode));
	int N,E;
	scanf("%d %d",&N,&E);
	graph=createGraph(graph,N,E);
	if(E!=0){
		for(int i=0;i<E;i++){
			scanf("%d %d",&e->v1,&e->v2);
			insertEdge(graph,e);
		}
	}
	return graph;
}
void DFS(MGraph graph,int v){
	graph->visited[v]=1;
	printf("%d ",v);
	for(int i=0;i<graph->Nv;i++){
		if(graph->visited[i]==0&&graph->G[v][i]==1){
			DFS(graph,i);
		}
	}
}
void listDFS(MGraph graph){
	for(int i=0;i<graph->Nv;i++){
		if(graph->visited[i]==0){
			printf("{ ");
			DFS(graph,i);
			printf("}\n");
		}
	}
}
Queue createQueue(Queue Q){
	Q=(Queue)malloc(sizeof(struct QNode));
	Q->front=Q->rear=0;
	return Q;
}
Queue push(Queue Q,int e){
	if(Q->front==(Q->rear+1)%100){
		return false;
	}
	else{
		Q->data[Q->rear]=e;
		Q->rear=(Q->rear +1)%100;
	}
	return Q;
}
int pop(Queue Q){
	int val;
	if(Q->front==Q->rear){
		return false;
	}
	else{
		val=Q->data[Q->front];
		Q->front=(Q->front+1)%100;
		return val; 
	}
}
void BFS(MGraph graph,int v){
	int val;
	Queue Q=createQueue(Q);
	push(Q,v);
	graph->visited[v]=1;
	while(Q->front!=Q->rear){
		val=pop(Q);
		printf("%d ",val);
		for(int i=0;i<graph->Nv;i++){
			if(graph->visited[i]==0&&graph->G[val][i]==1){
				push(Q,i);
				graph->visited[i]=1;
			}
		}
	}
}
void listBFS(MGraph graph){
	for(int i=0;i<graph->Nv;i++){
		if(graph->visited[i]==0){
			printf("{ ");
			BFS(graph,i);
			printf("}\n");
		}
	}
}
void reset(MGraph graph){
	for(int i=0;i<graph->Nv;i++){
		graph->visited[i]=0;
	}
}
int main(){
	MGraph graph=buildGraph(graph);
	listDFS(graph);
	reset(graph);
	listBFS(graph);
	return 0;
} 
